import java.util.LinkedList;
import java.util.Queue;

//class BTNode{
//    public char val;
//    public BTNode left;//左孩子
//    public BTNode right;//右孩子
//
//    public BTNode(char val) {
//        this.val = val;
//    }
//}
public class BinaryTree {

    public TreeNode root;//根结点

    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.right = H;
        return A;
    }
//    前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //    中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //    后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }


    /** 遍历思路
     * 获取树中节点的个数
     * @param root
     * @return
     */
//    1.
    public int size(TreeNode root) {
        int count = 0;
        if (root == null) {
            return 0;
        }
        count++;
        count += size(root.left);
        count += size(root.right);
        return count;
    }
//    2.
    int count = 0;
    public int size2(TreeNode root) {
//        int count = 0;//放里面每次都被count为0
        if (root == null) {
            return 0;
        }
        count++;
        size2(root.left);
        size2(root.right);
        return count;
    }

    /**子问题思路
     * 要求整棵树root的节点个数
     * root.left+root.right+1;
     */
    public int size3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }








    /**
     * 获取叶子节点个数
     * 遍历思路
     * 遍历到叶子节点 就让计数器++
     * root.left==null && root.right==null
     *
     *
     * 子问题思路： //绝大部分情况使用
     * 左树的叶子+右树的叶子=整棵树的叶子
     */

//    遍历思路
    int leftCount = 0;
    void getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left==null && root.right==null) {
            leftCount++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }
//    子问题思路
    int getLeafNodeCount2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left==null && root.right==null) {
//            当前的root是叶子节点
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }






    /**子问题思路
     * 获取k层节点的个数
     * @param root
     * @return
     */
    int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null || k < 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1);
    }


    /***
     **获取二叉树的高度
     * @param root
     * @return
     * 子问题的思路：
     * 左树的高度和右树的高度取最大值 然后+1 = 整棵树的高度
     */
//    1.
    int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left),getHeight(root.right)) + 1;
    }
//    2.
//    时间复杂度O(n)
//    空间复杂度(log(n))  就是树的高度（从root）开始 左边执行完再到右边
    int getHeight2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight2(root.left);
        int rightHeight = getHeight2(root.right);
        return leftHeight>rightHeight? leftHeight+1 : rightHeight+1;
    }




    /**
     *  检测值为value的元素是否存在
     * @param root
     * @param val
     * @return
     */
    TreeNode find(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;
//        从左树开始找
        TreeNode ret = find(root.left,val);
        if (ret != null) {
            return ret;//找到了返回
        }
//        从右树开始找
        ret = find(root.right,val);
        if (ret != null) {
            return ret;
        }
        return null;
    }







    /** 非递归更好做一些  （队列）：
     * 如果root不为空 将root放队列  然后拿出来放root左右孩子
     * 再拿一个 放拿出的左右孩子
     *
     * 判断一棵树是不是完全二叉树//包括没有节点的空树
     * @param root
     * @return
     */
    boolean isCompleteTree(TreeNode root) {
//        判断root是否为空 为空是完全二叉树
        if (root == null) return false;
//        创建队列
        Queue<TreeNode> queue = new LinkedList<>();
//        将根节点放入队列里
        queue.offer(root);
//        循环 如果队列不为空 那么以一个节点 放两个节点 知道拿出的是空
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
//        判断队列里是否全为空  如果有节点 那么就不是完全二叉树
        while (!queue.isEmpty()) {
            TreeNode top = queue.peek();
            if (top != null) {
                return false;
            }
            queue.poll();//判断一个删除一个
        }
        return true;
    }


//    这里要理解 如果是完全二叉树 队列里面全为空  那么它是有长度的  main3
}
